#include <vector>
#include <string>
#include <functional>
#include <string.h>

using namespace std;

// 1039. 多边形三角剖分的最低得分
class Solution1
{
public:
    int minScoreTriangulation(vector<int>& v) 
    {
        int n = v.size(), memo[n][n];
        memset(memo, -1, sizeof memo);
        function<int(int, int)> dfs = [&](int i, int j)
        {
            if(i + 1 == j) return 0; // 只有两个点，无法组成三角形
            int& ret = memo[i][j];
            if(ret != -1) return ret;
            
            ret = INT_MAX;
            for(int k = i + 1; k < j; ++k)
            {
                ret = min(ret, dfs(i, k) + dfs(k, j) + v[i] * v[j] * v[k]);
            }
            return ret;
        };

        return dfs(0, n - 1);
    }
};

// 1377. T 秒后青蛙的位置
class Solution2
{
public:
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) 
    {
        vector<vector<int>> g(n + 1);
        g[1] = {0}; // 减少额外判断
        for(auto& e : edges)
        {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        double ret = 0;

        function<long long(int, int, int)> dfs = [&](int x, int fa, int left) -> long long
        {
            if(left == 0) return x == target;
            if(x == target) return g[x].size() == 1;
            for(int y : g[x])
            {
                if(y != fa)
                {
                    auto prod = dfs(y, x, left - 1); // 寻找 target
                    if(prod) return prod * (g[x].size() - 1);
                }
            }
            return 0; // 未找到 target
        };

        auto prod = dfs(1, 0, t);
        return prod ? 1.0 / prod : 0;
    }
};

// 2246. 相邻字符不同的最长路径
class Solution3
{
public:
    int longestPath(vector<int>& parent, string s) 
    {
        int n = parent.size();
        vector<vector<int>> g(n);
        for(int i = 1; i < n; ++i) g[parent[i]].push_back(i);

        int ret = 0;
        function<int(int)> dfs = [&](int x)
        {
            int maxLen = 0;
            for(int y : g[x])
            {
                int len = dfs(y) + 1;
                if(s[x] != s[y])
                {
                    ret = max(ret, maxLen + len);
                    maxLen = max(maxLen, len);
                }  
            }

            return maxLen;
        };

        dfs(0);
        return ret + 1;
    }
};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// LCR 051. 二叉树中的最大路径和
class Solution4
{
public:
    int maxPathSum(TreeNode* root) 
    {
        int ret = INT_MIN;
        function<int(TreeNode*)> dfs = [&](TreeNode* node)
        {
            if(node == nullptr) return 0;

            int left = dfs(node->left);
            int right = dfs(node->right);
            ret = max(ret, left + right + node->val); // 两条链组成一条路径
            return max(max(left, right) + node->val, 0); // 当前子树的最大链和
        };

        dfs(root);
        return ret;
    }
};

// 543. 二叉树的直径
class Solution5
{
public:
    int diameterOfBinaryTree(TreeNode* root) 
    {
        int ret = INT_MIN;
        function<int(TreeNode*)> dfs = [&](TreeNode* node)
        {
            if(node == nullptr) return -1;

            int left = dfs(node->left);
            int right = dfs(node->right);
            ret = max(ret, left + right + 2);
            return max(left, right) + 1;
        };

        dfs(root);
        return ret;
    }
};

// 687. 最长同值路径
class Solution6
{
public:
    int longestUnivaluePath(TreeNode* root) 
    {
        int ans = 0;
        function<int(TreeNode*)> dfs = [&](TreeNode* node)
        {
            if(node == nullptr) return -1;

            int left = dfs(node->left) + 1;
            int right = dfs(node->right) + 1;
            if(node->left && node->left->val != node->val) left = 0;
            if(node->right && node->right->val != node->val) right = 0;
            ans = max(ans, left + right);
            return max(left, right);
        };

        dfs(root);
        return ans;
    }
};